package org.laizili.solution.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/sort-array-by-parity/">905. 按奇偶排序数组</a>
 * <p>
 * tags: 双指针; 排序算法思路应
 */
public class Problem905 {
    private static class Solution {
        public int[] sortArrayByParity(int[] nums) {
            int left = 0, right = nums.length - 1;
            while (left < right) {
                while (left < right && nums[left] % 2 == 0) {
                    // 奇数
                    left++;
                }
                while (left < right && nums[right] % 2 == 1) {
                    right--;
                }
                if (left < right)
                    swap(nums, left, right);
            }
            return nums;
        }

        private void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }

    // 冒泡 （奇数往后挪）
    private static class Solution2 {
        public int[] sortArrayByParity(int[] nums) {
            int idx = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] % 2 == 0) {
                    if (i != idx)
                        // 排除原地交换
                        swap(nums, i, idx);
                    idx++;
                }
            }
            return nums;
        }

        private void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }

    public static void main(String[] args) {
        Arrays.stream(new Solution2().sortArrayByParity(new int[]{3, 2, 1, 4})).forEach(System.out::println);
    }
}
